package offer;

import java.util.ArrayList;

//二叉树中和为某一值的路径
public class T25 {

     public class TreeNode {
     int val = 0;
     TreeNode left = null;
     TreeNode right = null;

     public TreeNode(int val) {
     this.val = val;

     }

     }
        public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {

            ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
            if (root==null||target<0) return lists;
            if (root.left==null&&root.right==null) {
                if (target==root.val) {
                    ArrayList<Integer> arrayList = new ArrayList<Integer>();
                    arrayList.add(root.val);
                    lists.add(arrayList);
                    return lists;
                }
                return lists;
            }
            ArrayList<ArrayList<Integer>> left = null;
            if (root.left!=null) {
              left = FindPath(root.left,target-root.val);
            }
            ArrayList<ArrayList<Integer>> right = null;
            if (root.right!=null) {
                right = FindPath(root.right,target-root.val);

            }

            if (left==null||right==null) {
                if (right!=null)  {
                    for (int i = 0; i < right.size(); i++) {
                        right.get(i).add(0,root.val);
                    }
                    return right;
                }
                else if (left!=null){
                    for (int i = 0; i < left.size(); i++) {
                        left.get(i).add(0,root.val);
                    }
                    return left;
                }
                return lists;
            }
            int i = 0;
            int j = 0;
            while (i<left.size()&&j<right.size()) {
                if (left.get(i).size()>right.get(j).size()) {
                     lists.add(left.get(i));
                     i++;
                }else {
                    lists.add(right.get(j));
                    j++;
                }
            }
            while (i<left.size()) lists.add(left.get(i++));
            while (j<right.size()) lists.add(right.get(j++));
            for (int ii = 0; ii < lists.size(); ii++) {
                lists.get(ii).add(0,root.val);
            }
            return  lists;
        }
        public void test() {
            TreeNode treeNode1 = new TreeNode(10);
            TreeNode treeNode2 = new TreeNode(5);
            TreeNode treeNode3 = new TreeNode(12);
            TreeNode treeNode4 = new TreeNode(4);
            TreeNode treeNode5 = new TreeNode(7);
            treeNode1.left=treeNode2;
            treeNode1.right=treeNode3;
            treeNode2.left = treeNode4;
            treeNode2.right=treeNode5;
            System.out.println(FindPath(treeNode1,15));
        }
        public static void main ( String[] args) {

            new  T25().test();
        }


}
